Content addressable memory (CAM) devices are often used to perform packet forwarding and classification operations in network switches and routers. A CAM device can be instructed to compare a comparand value, typically formed from one or more fields within the header of an incoming packet, with CAM words stored in an associative storage array within the CAM device. If the comparand matches a CAM word, the CAM device generates a CAM index that identifies the location of the matching CAM word within the storage array, and asserts a match flag to signal the match. The CAM index may then be used to index another storage array, either within or separate from the CAM device, to retrieve routing or classification information for the packet.
Compare operations within a CAM device are typically carried out on a bit-by-bit basis to determine if the comparand is identical to a CAM word. In some cases, selected bits within the comparand or the CAM word may be masked, enabling a range of comparands to match the CAM word. Unfortunately, the range of matching comparands achieved by masking is restricted in significant ways. First, the total range of matching comparands is limited to a power of two value (i.e., the inclusive difference between the highest and lowest matching comparands is 2N where N is the number of contiguous masked bits). A second restriction of a mask-based range is that the lower limit of the range generally must be an integral multiple of the total range (i.e., lower limit=0×2N, 1×2N, 2×2N, . . . ). If a match is desired for a range of comparands that is not a power of two or for which the lower limit is not an integral multiple of the total range, then multiple compare operations typically must be performed, each compare operation covering a portion of the overall range and meeting the above mask-based range restrictions. Referring to FIG. 1, for example, to determine whether a given comparand has an eight-bit source port field within the range 23 to 46, six different compare operations are needed (i.e., comparisons against values 23 and 46, and against mask-based ranges 31-24, 39-32, 43-40, and 45-44 as shown in FIG. 1). Similarly, six different compare operations are needed to determine whether a sixteen-bit destination port field within a comparand exceeds 1023 (i.e., comparisons against mask-based ranges 2047-1024, 4095-2048, 8191-4096, 16383-8192, 32767-16384, and 65535-32768 as shown in FIG. 1).
The multiple compare operations used to compare a comparand against a range of values may be performed successively, for example using different global mask values to define the different mask-based ranges, or they may be performed simultaneously by comparing a comparand to multiple CAM words in the CAM array, each CAM word constituting a range component that covers a portion of the overall range. Simultaneous comparison against multiple range components (i.e., single-cycle range compare) is faster than performing successive compare operations, but consumes a relatively large amount of CAM array storage. In the case of a binary CAM device, for example, each value in a given range must typically be stored in the CAM array to enable a single-cycle range compare. For instance, to permit the source port to range from 23 to 46 as shown in FIG. 1, 24 range components (i.e., 24 CAM words) would need to be stored in the CAM array. Alternatively, in the case of a ternary CAM device (i.e., a CAM device that includes storage for local mask values to permit per-row masking of CAM words), single-cycle range compare may be enabled by storing one range component in the CAM array for each mask-based range (setting the local mask value for the entry to define the mask-based range) and one range component for each of the exact values in the range. Referring to FIG. 1, for example, six range components may be stored in a ternary CAM device to cover the source port range from 23 to 46: exact value 23; mask-based range 31-24; mask-based range 39-32; mask-based range 43-40; mask-based range 45-44, and exact value 46.
The consumption of CAM array storage due to storage of multiple range components becomes more severe if more than one field within a comparand is permitted to range. Typically, the total number of range components that must be stored is the product of the numbers of range components required to define each distinct range. Referring to FIG. 1, for example, if a match is desired on any comparand for which the source port is between 23 to 46 (a range defined by 6 range components) and for which the destination port is greater than 1023 (a range also defined by 6 range components), then a total of 36 range components (i.e., 6×6) must be stored in a typical ternary CAM array to fully define the range of comparands which will match the source port and destination port ranges. The number of range components proliferates as other fields within the comparand are permitted to range (e.g., fields such as the source address, destination address, protocol, type of service, and virtual private network, etc.), consuming further storage space within the CAM array.